PC-SIG: World of Games/PC-SIG World of Games (CDRM1080710) (1993).iso/ENT/DISK1536.ZIP/LINSOLVE.LIS

File List | 1989-09-27 | 23KB | 518 lines

                           - 1 -
27th September, 1989                                       (Ver 2.9)

About TSLIN in General
======================

Apply  a question  mark ? with the program  call for the description
of the program, i.e. use LINSOLVE ? for the short instructions.

The  public domain version   of the  TSLIN package  may be  used and
distributed   freely    for   NON-COMMERCIAL,     NON-INSTITUTIONAL,
PRIVATE   usage,  provided it  is not  changed in  any way.  For ANY
other use (and/or the larger  version)  contact   the   author.   No
unauthorized charge  for  distributing this  program is allowed.  No
part of the package may be distributed separately.

An individually  registered version is  strictly for the  use of the
registrant. An identical program may NOT be running on more than one
computer at a time. Likewise a site licensed copy must not be run on
any  machine outside the  registered site. A  registration gives the
right  to use the program as stated here. It does not cover tutoring
or similar user support.

The  LINSOLVE program  is under  development. Comments  and contacts
are welcome. Feedback is solicited!
Internet address: [e-mail]       (preferred)
Funet address:    VAKK::SALMI
Bitnet address:   SALMI@FINFUN
FidoNet address:  2:515/1 (Micro Maniacs Opus; To: Timo Salmi).

The  author shall not be liable to the user for any direct, indirect
or  consequential loss arising from the use of, or inability to use,
LINSOLVE or this  package, or  any other  program or  file howsoever
caused. No warranty is  given that  the system  will work  under all
circumstances.

Timo Salmi
Professor of Accounting and Business Finance
School of Business Studies, University of Vaasa
P.O.BOX 297, SF-65101 Vaasa, Finland

CONTENTS:

    1. Introduction
    2. Linear Programming
    3. Sensitivity Analysis
    4. Floating Point Significance
    5. Linear Goal Programming
    6. Specialist's Corner
    7. Other Computers and Programs
    8. Release Notes for linsolve
    9. Selected References on Linear and Linear Goal Programming



.page
                           - 2 -


1. INTRODUCTION

   LINSOLVE solves linear programming ('LP') problems interactively.
LINSOLVE can also be used to solve linear GOAL programming problems.
For more details, see the later pages.
   The   maximum  capacity  of  the  program  is  80  variables,  55
constraints,  and 10  objectives. Notice,  however, that  the public
domain (PD) version will not handle more than 15 variables.
   You  give your problem in an 'as is' facsimile format from a file
or keyboard. The program will  ask  your  choices  for  the  options
available.  You  have the  choice of  maximizing or  minimizing, and
even printing out the Simplex-tableaux should you so wish.


2. LINEAR PROGRAMMING

Consider the following LP-problem

                                        (Name for row:)
   maximize z = 2X1 + 3X2               (Z)
   subject to
                 X1 + 2X2 +  X3 ≤ 13    (COND1)
                             X3 =  5    (COND2)
                -X1 +  X2 + 2X3 ≥  8    (COND3)
                         3 ≤ X3 ≤  6    (LO/UP)
                 X1,X2,X3 ≥ 0

Write LINSOLVE to call the program.

   LINSOLVE  first  prompts for   the method  of  input (keyboard or
file),  then  for the constraints,  and  next for the  objective(s).
The problem is given  to  LINSOLVE  in  facsimile  format  from  the
console or an ordinary text file:

COND1:  X1 + 2X2 +  X3 < 13
COND2:              X3 =  5     !exclamation marks (!) can be
COND3: -X1 +  X2 + 2X3 >  8     !used to include comments
LO:                 X3 >  3     !after and/or between rows
UP:                 X3 <  6
END
Z:     2X1 + 3X2
END                             !END can be replaced by LOPPU

   Each variable, constraint and objective must  be  named  using  a
unique  name.  The name  of a constraint,  objective or variable can
be up   to 10  characters  long.   Each constraint   (and objective)
name must  be followed by colon (:) to  separate it from the rest of
the row.

.page
                           - 3 -


   Spaces are ignored by   the   program.   You   can,   of  course,
utilize spaces to clarify the structure of the problem.
   Lower  and  upper cases  are not  differentiated.  (Thus e.g. "b"
and  "B" are  treated the  same.) The  alphabet consist  of A-Z.
   A row   can be continued using an   ampersand (&). E.g. the third
constraint could have been given as
      COND1:  X1 + 2X2 &
              + X3 < 13
Alternatively, * can be  used  instead  of  &  as  the  continuation
marker.
   LINSOLVE  checks  and reports syntax  errors before proceeding to
solve the problem. If the input is taken from a file, the program is
aborted when an  error is encountered.  If the task  is entered from
the keyboard,  and the error is not  fatal, LINSOLVE prompts for the
relevant constraint (or objective) again.
   The  program also  prompts  for  the  choice  of  output   device
(screen  or  file),  whether  the objective is  to minimize (if not,
then maximize), and whether the Simplex-tableaux are printed.
   Using systematic   extension such  as  .SOL  in the   output file
name is commendable if output is directed to a file.
   Output can be directed to the screen by giving CON, or no name at
all, to the output file.


3. SENSITIVITY ANALYSIS

   LINSOLVE  optionally  performs  a  sensitivity  analysis  on  the
coefficients  of the objective function, and the right-hand sides of
the constraints.
   The sensitivity analysis  for the  objective function  solves the
range of objective  function coefficients  which retain  the optimum
solution. (The  definition of retaining an  optimum solution is that
the variables in the basis remain the same. In the case of objective
function  sensitivity analysis also the values of the optimum values
of the variables remain unchanged.)
   The sensitivity analysis for  the  right-hand  sides  give  their
corresponding ranges retaining the optimum basis. (In this case, the
values of the variables in the optimum basis would be changed.)
   The  sensitivity analysis is only performed if certain conditions
are met.  First, it is  limited to linear  programming problems with
one objective.  Sensitivity analysis  is thus  not performed  in the
case  of linear goal  programming problems. Second,  the analysis is
performed only if the problem has a feasible, non-infinite solution.
Third,  although LINSOLVE can,  and will, solve  problems which have
negative  right-hand sides, no sensitivity analysis is performed for
such tasks.

.page
                           - 4 -


4. FLOATING POINT SIGNIFICANCE

   When   formulating the original LP problem  do not use very large
or  small coefficients in  the   constraints  or  the  objective(s).
Although seldom recognized,  this  requirement  is  endemic  in most
linear  programming codes. This  results  from  the  fact  that  the
accuracy  of  real  numbers  is  always  more  or  less  limited  in
computing,  even  if  mathematically  linear  programming  poses  no
problems.

Thus, instead of e.g
   400000X1 + 800000X2 < 2000000
or
   0.004X1 + 0.008X2 < 0.02
use
   4X1 + 8X2 < 20

   In   particular, do  not to mix   large and small coefficients in
the same problem.
   In   business applications, a change of  unit of the variables is
often a useful trick for  avoiding  problems  caused  by  computers'
limited accuracy.
   Also avoid   the mistake  of giving   the same  constraint twice,
since such linear  dependency   can   make   the   Simplex-algorithm
fail.
   If the program terminates in an error message:
      Runtime error 205 at xxxx:xxxx.
which indicates a  floating point overflow,  it is not  a failure of
the program code, but a result of a bad scaling of your LP task.


5. LINEAR GOAL PROGRAMMING

   As   with linear  programming, it  is  assumed  that the  user is
fully  familiar with the concept of linear goal programming. If not,
the  text-books  by  Sang  M.  Lee  (Goal  Programming  for Decision
Analysis)  and James P. Ignizio  (Goal Programming) are recommended.
See the references at the end of these instructions.
   Consider  the following linear goal  programming problem where P1
denotes the  highest priority level. Note  that the standard of goal
programming is minimization.

   Minimize Z = P1(d2+) + 2P2(d1-) + 3P2(d2-)
   subject to
                 X1 + 2X2                   > 2   (ROW1)
                4X1 + 2X2 + d1-             = 4   (ROW2)
                3X1 + 5X2       + d2- - d2+ = 3   (ROW3)
                       X2                   < 5   (ROW4)
                 X1,X2,d1-,d2-,d2+ > 0

.page
                           - 5 -


The corresponding input to LINSOLVE should be

ROW1:  X1 + 2X2                   > 2
ROW2: 4X1 + 2X2 + D1N             = 4
ROW3: 3X1 + 5X2       + D2N - D2P = 3
ROW4:        X2                   < 5
END
P1: D2N           !Highest priority first
P2: 2D1N + 3D2N
END


5. SPECIALIST'S CORNER

The Algorithm

   LINSOLVE  applies   the   two-stage  Simplex-method.  (In  linear
goal   programming    a   corresponding   multiple-stage    Simplex-
method.)  In  both   cases,   artificial  variables  and   objective
(called   "Extra" in  LINSOLVE_EXE) are added to the problem. In the
first stage the  algorithm  tries  to  get  rid  of  the  artificial
variables. (If  it can't, the  solution of the   original problem is
not feasible.  If this is the case, LINSOLVE duly reports the fact.)
In the subsequent stage(s) LINSOLVE  finds   the  solution   to  the
problem given  by the user.
   If the  user request LINSOLVE to  print the Simplex-tableaux, the
Extra    objective   and     Extra    variables     are    included.
Similarly,  the Extra objective  appears  on  the   listing  of  the
optimum  solution.  (Its value  will become   zero, if  the original
problem has a feasible solution.)


Altering the zero criterion

   The accuracy   of  the   floating  point   arithmetic  is  eleven
significant digits in  the Turbo  Pascal 4.0  (internal) arithmetic.
Round-off errors  tend accumulate   in  the   Simplex-algorithm.  To
counter  this  fact, all elements less  than a zero-limit (5E-6) are
set  to exact zero  at each iteration.  An experienced user may want
to alter this limit. This can be done by giving the new value as the
parameter of the program call. For example: LINSOLVE 0.0001
   The  optional   statistics  include  the   number  of  round-offs
performed by  the program. The  smaller the figure,  the less likely
the problems due to the floating point arithmetic.

.page
                           - 6 -

7. OTHER COMPUTERS AND PROGRAMS

   The LINSOLVE program  is  also  available  for  the  Sinclair  QL
computer. It is part of a Public Domain library for QUANTA members.
   LINSOLVE  has also been programmed for the VAX 11/750 computer at
the Vaasa University, by  the  author,  but  the  input  and  output
commands  of the VAX "TAVOPT" are in Finnish, and the program is not
public domain.
   The package for drawing LP programs of two dimensions, TSDRAW, is
available separately for the PC.


8. RELEASE NOTES

   In version 1.1 a  bug preventing  the input  of more  than (only)
eleven constraints was corrected.

   In version 1.2 the sensitivity analysis was added to the program.
Also  some minor  improvements were  made in  the defaults,  and the
information  about the solution, when the  solution is directed to a
file. The  algorithm has been  tested with more  problems with known
solutions. The  rare special situations  where the Simplex-algorithm
is known to fail, have not yet been tested. (See notes on ver 2.1.)

   In version 1.3 some minor stylistic changes were made.

   In  version 1.4 the possibility of entering a header on each page
of  output was added. If the very first line of the task starts with
!! as in
            !!A tiny task
            E1: X1 + 2X2 < 2
            END
            MAX: 3X1 + 5X2
            END
then the text  "A tiny task"  is used as  a header for  each page of
output,  if the output is directed to a file. !! indicates a header,
a single ! an ordinary comment.

   In version 1.5 more error checks have been added to safeguard the
user  against giving input that could not be parsed into a proper LP
format. E.g. it is  now  checked  that  a  continuation  row  really
follows  after the use the  the continuation marker (&  or *) on the
previous row.

   Version  1.6 introduces a built-in help  to linsolve. Help can be
invoked  by entering ? when the program asks for input. From version
1.6  it is possible to use the  Scandinavian characters (Å, Ä, Ö) in
the variable, constraint and objective names.

.page
                           -  7 -

   Version 1.7 uses an improved directory utility. If the input file
is not found, the user is given the option of listing directories on
the screen without having to exit LINSOLVE. The directory mask (file
definition) is now much more relaxed, and almost the same as for the
MS-DOS dir  command. More information  on this feature  can be found
within the TSUTIL package. (See the TSPROG.INF file.)

   Version 1.8 introduces mostly internal changes not visible to the
user.

   In version  1.9 an attempt to rewrite  a read-only output file no
longer crashes the program.

   Version  2.0 improves  the speed  of reading  the problem  from a
file.

   Version 2.1: A linear programming problem can generally be stated
as
        max  cx
        s.t.
             Ax ≤ b
              x ≥ 0
Version  2.1 introduces an index of the accuracy of the solution. In
linear programming computer implementations the round-off errors may
cause problems,  and even deviations from  optimality. To assess the
effect of  these problems on the current  task the final tableau the
is recalculated from the  inverse  matrix  of  the  base.  Then  the
original  solution tableau is compared with the recalculated tableau
by  defining four different (in)accuracy measures. These are the sum
of absolute deviations  in the left-hand  side matrix A,  the sum of
absolute deviations  in the solution  vector b, and  sum of absolute
deviations   in  the  simplex  coefficients.  The  simplex-algorithm
version  used in this program seeks the optimum by trying to get all
the simplex coefficients to be non-positive. The fourth (in)accuracy
measure is  the  sum  of  the  free  recalculated  positive  simplex
coefficients. The  four inaccuracy measures  are called respectively
a-inaccuracy, b-inaccuracy, z-inaccuracy,  and  non-optimality.  The
overall inaccuracy reported together with the solution is simply the
sum of these four inaccuracies.
   Another novel feature in version  2.1  is  checking  the  special
cases  caused by  linear dependencies  and point-like  solutions. In
both  these cases (see the linear programming literature) artificial
(Extra)  variable(s) may remain in the optimal basis but as zero(s).
If the solution of a linear programming or a linear goal programming
problem is non-feasible then the value of the artificial variable(s)
staying in basis  will be  non-zero. These  zero/non-zero conditions
are now detected by LINSOLVE.

.page
                           - 8 -

   Parsing the  problem (i.e. reading and  interpreting it) has been
made faster, as has been computing the iterations.
   The  range of the zero described  in an earlier section "Altering
the  Zero Criterion" has been made wider, and it is now possible not
to  alter the small elements at all. This is achieved by calling the
program by LINSOLVE 0. This  is  not  advisable,  though,  since  it
usually leads to suboptimal solutions.

   Version  2.2 introduces the choice between starting each new page
of  output (when directed to  a file) either with  a formfeed or two
blank lines (earlier  it  was  always  a  formfeed).  If  output  is
directed to the printer, that is to the file PRN, the user now has a
choice of the left margin between 0 and 20.

   Version   2.3:  The  default  output  gives  the  values  of  the
variables, slacks, objectives,  and  the  shadow  prices,  i.e.  the
simplex coefficients of  the  variables  in  the  first  basis.  The
simplex coefficients  of the the original  variables have been added
to the default output in version 2.3. They are given under the title
REDUCED  COST. (For interpreting the shadow prices and reduced costs
see the appropriate literature.)
   If the output is directed to a printer (that is to file PRN), the
online/offline  status of the printer is now tested immediately, and
the user  is notified.  (In the  program code,  this is  achieved by
using the interrupts for the testing, instead of IOResult checking.)

   Version  2.4: The program  has been recompiled  with Turbo Pascal
5.0. The bug  preventing reading  a read-only  file has  been fixed.
(This bug was actually  due  to  Turbo  Pascal  4.0  documentation.)
Furthermore, the program  now augments  pathnames to  filenames when
appropriate.

   Version  2.5: Most importantly, new files  have been added to the
package. See  the  separate  documentation  in  MPS2EQU.INF  and  in
chapter 9.  As to linsolve, if an input  file is not found, the user
has been  given  the  option  of  listing  directories  from  within
linsolve. This directory routine  has  been  rewritten  for  a  more
relaxed  syntax and tighter code. A bug in the heap control has been
fixed. This  caused problems in rare cases  during the out of memory
condition.   The  maximum  number  of   objectives  in  linear  goal
programming was one too small because of a bug. This has been fixed.


.page
                           - 9 -


   Version 2.6: Modern technology (sometimes not so modern :-) makes
it possible to project a computer screen using an overhead projector
onto  a wall screen e.g. for classroom  usage. In trying this out, I
noticed,  that it would be useful to have the option of changing the
linsolve colors. The consequent new usage of the LINSOLVE call is

   LINSOLVE [/fx (foreground color)] [/bx (background color)]
            [/zxx.x (zero criterion)] [/h (help)]

The simplest  way of changing the colors  is using just LINSOLVE /f,
which  will give you a white text on black background. The /f and /b
parameters  can include  a color  number ranging  from 0-15  for the
foreground,  and 0-7 for the background.   For the color map, either
experiment, or see a Turbo Pascal manual for TextColor constants.
   I  have made a couple  of minor internal changes  to speed up the
program at certain phases. Also, the help screen can now be directed
to a file, or to the printer. For this, use LINSOLVE /h > PRN.

   Version  2.7: This revision includes  two major enhancements. The
capacity  of the program  has been increased  from 55x80 constraints
and variables  to 80x120. The second  enhancement is the possibility
of input recall with line-editing.
   A well-known bottle-neck of MsDos is the fact that the Intel 808x
processors limit  array sizes to  64K. To use  larger arrays special
techniques are needed.  LINSOLVE version  2.7 employs  the so-called
huge-arrays  method. This means enhanced capacity, but also slightly
slower code.  LINSOLVE still runs  in the memory,  and remains fast,
contrary to  many other LP  programs using sloo..oow  disk access in
iterating.
   The  possibility of input recall with line-editing is introduced.
This means  that in  giving input  from the  keyboard, you  have the
following   extra  input  keys  available:  Home,  End,  CursorLeft,
CursorRight,  CursorUp, Delete, and Esc. CursorUp is the recall key.
The  others are self-explanatory. This option is particularly useful
in giving the linear programming task from the keyboard in classroom
usage. That  is the  primary reason  why I  added this  feature into
linsolve.

   Version 2.8:  The  public  domain  task  size  limits  have  been
increased to 55x25 from  55x15.  Line-editing  has  been  made  more
context sensitive, and the Insert key has been made functional.

   Version 2.9:  If output  is directed  to a  file, the  file ready
message now also  contains the  file size  in bytes.  The acceptable
file names now also include the ( ) and _ characters.

.page
                           - 10 -


9. SELECTED REFERENCES ON LINEAR AND LINEAR GOAL PROGRAMMING

Gass,  Saul I. Linear Programming:  Methods and Applications. Second
  edition. McGraw-Hill Book Company, 1964.

Hadley,  G. Linear  Programming. Addison-Wesley  Publishing Company,
  1962. (This is  one of the  classics on the  mathematics of linear
  programming.)

Ignizio, James  P.   Goal  Programming  and  Extensions.   Lexington
  Books, 1976.

Ignizio, James p.   "A  Review  of  Goal  Programming:  A  Tool  for
  Multiobjective Analysis",  Journal  of  the  Operational  Research
  Society, Vol. 29, No. 11 (November 1978), ss. 1109-1119.

Jennergren, Peter L.  "Linear programming on  a micro -  The case of
  the  Apple II", European Journal of Operational Research, Vol. 19,
  No. 2 (February 1985), pp. 212-216.

Jääskeläinen,  Veikko.    Lineaarinen  optimointi   ja  budjetointi.
  Ekonomia-sarja 18.  Tapiola: Weilin+Göös, 1972.

Jääskeläinen,  Veikko.  Linear  Programming  and  Budgeting.  Malmö,
  Sweden: Student-litteratur,  1975.  (One  of  the  very  few  good
  applications oriented text-books  on  the  utilization  of  linear
  programming. Covers also linear goal programming.)

Kallio,  Markku. A  Corporate Planning  Model. Research  Paper D-17.
  Helsinki School of Economics, January 1977.

Lee,  Sang M.  Goal Programming for Decision Analysis. Philadelphia:
  Auerbach Publishers Inc., 1972.  (out of print?)

Perälä,    Tarja.    Tavoiteoptimointi    ja   investointipäätökset.
  Tutkielma   kvantitatiivisen  yritysanalyysin  koulutusohjelmassa.
  Vaasan korkeakoulu 1982. (Sisältää kattavan lähdeluettelon.)

Salmi, Timo. Lineaarinen optimointi ja sen soveltaminen. Täydennetty
  painos.  Vaasan  korkeakoulu,  1981.  (Yksinkertaistettu  johdatus
  aiheeseen.)

Schniederjans, Mark  J.  Linear  Goal  Programming.  Princeton,  New
  Jersey:  Petrocelli  Books,  1984.  (Contains  a  lot  of  further
  references.)

Stadler, Hartmut  &  Maren  Groenenveld  &  Heidrun  Hermanssen.  "A
  Comparison  of LP  Software on  Personal Computers  for Industrial
  Applications",  European Journal of Operational Research. Vol. 35,
  No. 2 (May 1988), pp. 146-159.